Introduction

This vignette illustrates the use of INLA for spatial prediction using examples from Blangiardo and Cameletti (2015) and Illian, Sørbye, and Rue (2012). For prediction of continuous spatial processes, the stochastic partial differential equations (SPDE) approach is used to approximate the process through an areal Gaussian Markov random field (GMRF) representation.

GMRF Background

Blangiardo and Cameletti (2015) section 6.1.

SPDE Background

Find Lindgren et. al. (2011) and fill in motivation

Geostatistics Example

Toy dataset from Blangiardo and Cameletti (2015).

# Plot the data.
plot(s2 ~ s1, col = rgb(SPDEtoy$y / max(SPDEtoy$y), 0, 0), data = SPDEtoy, pch = 19, asp = 1, main = 'Toy Data')

# Create a mesh for the SPDE method and then plot it.
toy_mesh <- inla.mesh.2d(as.matrix(SPDEtoy[,c('s1', 's2')]), max.edge = c(0.1, 0.2))
plot(toy_mesh, asp = 1)
points(SPDEtoy$s1, SPDEtoy$s2, col = rgb(SPDEtoy$y / max(SPDEtoy$y), 0, 0, 0.5), pch = 20)

# SPDE projector matrix for estimation.
A_est <- inla.spde.make.A(toy_mesh, as.matrix(SPDEtoy[,c('s1', 's2')]))

# Initialize exponential covariance structure for SPDE.
spde <- inla.spde2.matern(mesh = toy_mesh, alpha = 2)

# Set up stack for estimation.
stack_index <- inla.spde.make.index(name = 'spatial_field', n.spde = spde$n.spde)
stack_est <- inla.stack(data = list(y = SPDEtoy$y), A = list(A_est), effects = list(c(stack_index, list(intercept = 1))), tag = 'est')

# Create a grid for prediction.
toy_nx <- 50
toy_ny <- 50
toy_grid <- expand.grid(x = seq(0, 1, length.out = toy_nx), y = seq(0, 1, length.out = toy_ny))

# SPDE projector matrix for prediction.
A_pred <- inla.spde.make.A(mesh = toy_mesh, loc = as.matrix(toy_grid))

# Set up stacks for prediction.
stack_latent <- inla.stack(data = list(xi = NA), A = list(A_pred), effects = list(stack_index), tag = 'pred_latent')
stack_response <- inla.stack(data = list(y = NA), A = list(A_pred), effects = list(c(stack_index, list(intercept = 1))), tag = 'pred_response')

# Join all three stacks.
stacks <- inla.stack(stack_est, stack_latent, stack_response)

# Fit the model with INLA.
toy_fit <- inla(
  y ~ -1 + intercept + f(spatial_field, model = spde),
  data = inla.stack.data(stacks),
  control.predictor = list(A = inla.stack.A(stacks), compute = TRUE)
)

# Output posterior summaries.
toy_fit$summary.fixed
toy_fit$summary.hyperpar
# Extract posterior mean of latent spatial field.
index_latent <- inla.stack.index(stacks, tag = 'pred_latent')$data
post_mean <- toy_fit$summary.linear.predictor[index_latent, 'mean']
post_sd <- toy_fit$summary.linear.predictor[index_latent, 'sd']

# Plot the posterior mean and SD of the latent spatial field.
plot(im(matrix(post_mean, nrow = toy_nx, ncol = toy_ny), xrange = range(toy_grid$x), yrange = range(toy_grid$y)), main = 'Posterior Mean of Spatial Field')
points(SPDEtoy$s1, SPDEtoy$s2, col = rgb(SPDEtoy$y / max(SPDEtoy$y), 0, 0, 0.5), pch = 20)

plot(im(matrix(post_sd, nrow = toy_nx, ncol = toy_ny), xrange = range(toy_grid$x), yrange = range(toy_grid$y)), main = 'Posterior SD of Spatial Field')
points(SPDEtoy$s1, SPDEtoy$s2, col = rgb(SPDEtoy$y / max(SPDEtoy$y), 0, 0, 0.5), pch = 20)

Bei Dataset and inlabru

Example from Møller and Waagepetersen (2007), Beilschmiedia pendula Lauraceae locations in a plot in Panama. bei dataset in spatstat (Baddeley and Turner 2005).

# Plot the full point pattern.
plot(bei, pch = '.', cols = 'black', main = 'Realized Point Pattern')

bei_corners <- vertices.owin(Window(bei))
bei_domain <- cbind(bei_corners$x, bei_corners$y)
bei_full_mesh <- inla.mesh.2d(cbind(bei$x, bei$y),
                              cutoff = 50, max.edge = c(50, 100),
                              loc.domain = bei_domain)
plot(bei_full_mesh, asp = 1)
plot(Window(bei), border = 'blue', add = TRUE)
points(bei, pch = '.', col = 'blue')

bei_full_spdf <- as.SpatialPoints.ppp(bei)
# CHECK PRIORS!
matern_full <- inla.spde2.pcmatern(bei_full_mesh,
                                   prior.sigma = c(0.1, 0.99),
                                   prior.range = c(5, 0.01))
cmp_full <- coordinates ~ mySmooth(map = coordinates, model = matern_full) + Intercept
bei_full_lgcp <- lgcp(cmp_full, bei_full_spdf)
lambda_full <- predict(bei_full_lgcp, pixels(bei_full_mesh), ~ exp(mySmooth + Intercept))

# Plot posterior means and posterior sd.
plot(lambda_full)
plot(Window(bei), border = 'white', add = TRUE)
points(bei, pch = '.', col = 'white')

plot(lambda_full['sd'])
plot(Window(bei), border = 'white', add = TRUE)
points(bei, pch = '.', col = 'white')

# Take a sample of quadrats and plot the observed point pattern.
set.seed(84323)
n_quads <- 10
botleft <- cbind(runif(n_quads, 0, 950), runif(n_quads, 0, 450))
bei_interior <- lapply(seq_len(nrow(botleft)), function(r){return(
    cbind(
      botleft[r, 1] + c(0, 0, 50, 50),
      botleft[r, 2] + c(0, 50, 50, 0)
    )
  )})
bei_win <- do.call(
  union.owin,
  apply(botleft, 1, function(x){return(
    owin(x[1] + c(0, 50), x[2] + c(0, 50))
  )})
)
bei_hole <- bei[complement.owin(bei_win)]
bei_samp <- bei[bei_win]
bei_window_full <- Window(bei)

plot(bei_hole, main = 'Observed Subregion', pch = '.', cols = 'black')

bei_hole_mesh <- inla.mesh.2d(cbind(bei_hole$x, bei_hole$y),
                              cutoff = 50, max.edge = c(50, 100),
                              loc.domain = bei_domain)
plot(bei_hole_mesh, asp = 1)
plot(Window(bei), border = 'blue', add = TRUE)
points(bei_hole, pch = '.', col = 'blue')

bei_hole_spdf <- as.SpatialPoints.ppp(bei_hole)
# CHECK PRIORS!
matern_hole <- inla.spde2.pcmatern(bei_hole_mesh,
                                   prior.sigma = c(0.1, 0.99),
                                   prior.range = c(5, 0.01))
cmp_hole <- coordinates ~ mySmooth(map = coordinates, model = matern_hole) + Intercept
bei_hole_lgcp <- lgcp(cmp_hole, bei_hole_spdf)
lambda_hole <- predict(bei_hole_lgcp, pixels(bei_hole_mesh), ~ exp(mySmooth + Intercept))

# Plot posterior means and posterior sd.
plot(lambda_hole)
plot(Window(bei_hole), border = 'white', add = TRUE)
points(bei_hole, pch = '.', col = 'white')

plot(lambda_hole['sd'])
plot(Window(bei_hole), border = 'white', add = TRUE)
points(bei_hole, pch = '.', col = 'white')

plot(bei_window_full, main = 'Observed Sample')
plot(bei_win, add = TRUE)
plot(bei_samp, pch = '.', cols = 'black', add = TRUE)

bei_samp_mesh <- inla.mesh.2d(cbind(bei_samp$x, bei_samp$y),
                              cutoff = 50, max.edge = c(50, 100),
                              loc.domain = bei_domain)
plot(bei_samp_mesh, asp = 1)
plot(Window(bei), border = 'blue', add = TRUE)
plot(Window(bei_samp), border = 'blue', add = TRUE)
points(bei_samp, pch = '.', col = 'blue')

bei_samp_spdf <- as.SpatialPoints.ppp(bei_samp)
# CHECK PRIORS!
matern_samp <- inla.spde2.pcmatern(bei_samp_mesh,
                                   prior.sigma = c(0.1, 0.99),
                                   prior.range = c(5, 0.01))
cmp_samp <- coordinates ~ mySmooth(map = coordinates, model = matern_samp) + Intercept
bei_samp_lgcp <- lgcp(cmp_samp, bei_samp_spdf)
lambda_samp <- predict(bei_samp_lgcp, pixels(bei_samp_mesh), ~ exp(mySmooth + Intercept))

# Plot posterior means and posterior sd.
plot(lambda_samp)
plot(Window(bei), border = 'white', add = TRUE)
plot(Window(bei_samp), border = 'white', add = TRUE)
points(bei_samp, pch = '.', col = 'white')

plot(lambda_samp['sd'])
plot(Window(bei), border = 'white', add = TRUE)
plot(Window(bei_samp), border = 'white', add = TRUE)
points(bei_samp, pch = '.', col = 'white')

Bei Dataset with gridding

centers <- gridcenters(dilation(bei_window_full, 40), 40, 20)
dx <- sum(unique(centers$x)[1:2] * c(-1, 1)) / 2
dy <- sum(unique(centers$y)[1:2] * c(-1, 1)) / 2
bei_df <- data.frame(x = centers$x, y = centers$y,
                     count = NA_integer_, area = NA_real_)

for(r in seq_len(nrow(bei_df))){
  bei_df$count[r] <- sum(bei$x >= bei_df$x[r] - dx &
                         bei$x < bei_df$x[r] + dx &
                         bei$y >= bei_df$y[r] - dy &
                         bei$y < bei_df$y[r] + dy)
  bei_df$area[r] <- area(Window(bei)[owin(c(bei_df$x[r] - dx, bei_df$x[r] + dx), c(bei_df$y[r] - dy, bei_df$y[r] + dy))])
}

par(mar = c(0.5, 0, 2, 2))
plot(im(t(matrix(bei_df$count, nrow = length(unique(bei_df$x)))), unique(bei_df$x), unique(bei_df$y), unitname = 'meters'), ncolcours = range(bei_df$count) %*% c(-1, 1) + 1, main = 'Binned Tree Counts')
plot(bei_window_full, border = 'white', add = TRUE)
points(bei, pch = '.', col = 'black')

# SPDE projector matrix for estimation.
full_A_est <- inla.spde.make.A(bei_full_mesh, as.matrix(bei_df[bei_df$area > 0, c('x', 'y')]))

# Initialize exponential covariance structure for SPDE.
full_spde <- inla.spde2.matern(mesh = bei_full_mesh, alpha = 2)

# Set up stack for estimation.
stack_index <- inla.spde.make.index(name = 'spatial_field', n.spde = full_spde$n.spde)
stack_est <- inla.stack(data = list(count = bei_df$count[bei_df$area > 0], larea = log(bei_df$area[bei_df$area > 0])), A = list(full_A_est), effects = list(c(stack_index, list(intercept = 1))), tag = 'est')

# SPDE projector matrix for prediction.
full_A_pred <- inla.spde.make.A(mesh = bei_full_mesh, loc = as.matrix(bei_df[,c('x', 'y')]))

# Set up stacks for prediction.
stack_latent <- inla.stack(data = list(xi = NA), A = list(full_A_pred), effects = list(stack_index), tag = 'pred_latent')
stack_response <- inla.stack(data = list(count = NA), A = list(full_A_pred), effects = list(c(stack_index, list(intercept = 1))), tag = 'pred_response')

# Join all three stacks.
stacks <- inla.stack(stack_est, stack_latent, stack_response)

# Fit the model with INLA.
bei_full_fit <- inla(
  count ~ -1 + intercept + f(spatial_field, model = full_spde),
  offset = larea, family = 'poisson',
  data = inla.stack.data(stacks),
  control.predictor = list(A = inla.stack.A(stacks), compute = TRUE)
)

# Output posterior summaries.
bei_full_fit$summary.fixed
bei_full_fit$summary.hyperpar
# Extract posterior mean of latent spatial field.
index_pred <- inla.stack.index(stacks, tag = 'pred_latent')$data
post_mean <- bei_full_fit$summary.linear.predictor[index_pred, 'mean']
post_sd <- bei_full_fit$summary.linear.predictor[index_pred, 'sd']

# Plot the posterior mean and SD of the latent spatial field.
plot(im(t(matrix(post_mean, nrow = length(unique(centers$x)), ncol = length(unique(centers$y)))), unique(centers$x), unique(centers$y)), main = 'Posterior Mean of Spatial Field')
plot(bei_window_full, add = TRUE)
points(bei, pch = '.', col = 'black')

plot(im(t(matrix(post_sd, nrow = length(unique(centers$x)), ncol = length(unique(centers$y)))), unique(centers$x), unique(centers$y)), main = 'Posterior SD of Spatial Field')
plot(bei_window_full, add = TRUE)
points(bei, pch = '.', col = 'black')

beihole_df <- data.frame(x = centers$x, y = centers$y,
                         count = NA_integer_, area = NA_real_)

for(r in seq_len(nrow(beihole_df))){
  beihole_df$count[r] <- sum(bei_hole$x >= beihole_df$x[r] - dx &
                             bei_hole$x < beihole_df$x[r] + dx &
                             bei_hole$y >= beihole_df$y[r] - dy &
                             bei_hole$y < beihole_df$y[r] + dy)
  beihole_df$area[r] <- area(Window(bei_hole)[owin(c(beihole_df$x[r] - dx, beihole_df$x[r] + dx), c(beihole_df$y[r] - dy, beihole_df$y[r] + dy))])
}

par(mar = c(0.5, 0, 2, 2))
plot(im(t(matrix(beihole_df$count, nrow = length(unique(beihole_df$x)))), unique(beihole_df$x), unique(beihole_df$y), unitname = 'meters'), ncolcours = range(beihole_df$count) %*% c(-1, 1) + 1, main = 'Binned Tree Counts')
plot(Window(bei_hole), border = 'white', add = TRUE)
points(bei, pch = '.', col = '#00000040')

Bei Dataset with Simpson et al. (2016) method

This method relies upon the Lindgren, Rue, and Lindström (2011) approximation of the latent Gaussian field as a linear combination of a finite number of basis functions represented as a GMRF on the nodes of a triangulation of the space. Simpson et al. (2016) use the triangulation for numerical integration of the intensity function and show that the LGCP likelihood factors into the joint distribution of independent Poisson random variables corresponding to the points of the point pattern and the nodes of the triangulation. The model fitting proceeds using INLA to fit a Poisson model to pseudodata.

The pseudodata are constructed as follows.

Then \(y_{i} \sim Poisson(\alpha_{i}\eta_{i})\) where \(\log(\eta_{i})\) is the SPDE representation of the GF at the location of the \(i\)th pseudodatum. See the paper for tedious notation regarding the definition of \(\eta_{i}\). Ultimately, the nodes become Poisson random variables with means equal to the intensity at that their respective locations, observed points become Poisson random variables with means of 1, and the likelihood is approximately proportional to

\[ \prod_{i=1}^{p+n} \eta_{i}^{y_{i}} \exp(-\alpha_{i} \eta_{i}). \]

(Is there a missing \(\alpha_{i}\)?)

# Parameters to experiment with.
MAX_EDGE_LENGTH <- 25

boundary <- inla.mesh.segment(loc = do.call(cbind, vertices.owin(Window(bei))))
mesh <- inla.mesh.create(
  boundary = boundary,
  refine = list(max.edge = MAX_EDGE_LENGTH)
)

plot(mesh, main = 'Mesh for Bei Site')
points(bei, pch = 19, cex = 0.25, col = 'red')

pts <- cbind(bei$x, bei$y)

# Contruct the SPDE A matrix for nodes and points.
nV <-mesh$n
nData <- dim(pts)[1]
LocationMatrix <- inla.mesh.project(mesh, pts)$A
IntegrationMatrix <- sparseMatrix(i = 1:nV, j = 1:nV, x = rep(1, nV))
ObservationMatrix <- rbind(IntegrationMatrix, LocationMatrix)

# Get the integration weights.
IntegrationWeights <- diag(inla.mesh.fem(mesh)$c0)
E_point_process <- c(IntegrationWeights, rep(0, nData))

# Create the psuedodata.
fake_data <- c(rep(0, nV), rep(1, nData))

# Fit model to full site.
spde <- inla.spde2.matern(mesh)
formula <- y ~ -1 + intercept + f(idx, model = spde) # No covariates.
data <- list(y = fake_data, idx = 1:(nV), intercept = rep(1, nV))
result_full <- inla(
  formula,
  data = data,
  family = 'poisson',
  control.predictor = list(A = ObservationMatrix),
  E = E_point_process,
  verbose = TRUE
)
summary(result_full)

Call:
c("inla(formula = formula, family = \"poisson\", data = data, E = E_point_process, ",  "    verbose = TRUE, control.predictor = list(A = ObservationMatrix))" )

Time used:
 Pre-processing    Running inla Post-processing           Total 
         0.2388         44.7314          0.0567         45.0269 

Fixed effects:
             mean     sd 0.025quant 0.5quant 0.975quant    mode   kld
intercept -5.8164 0.5817    -6.9936  -5.8135    -4.6551 -5.8083 4e-04

Random effects:
Name      Model
 idx   SPDE2 model 

Model hyperparameters:
                 mean     sd 0.025quant 0.5quant 0.975quant   mode
Theta1 for idx  2.597 0.0542      2.493    2.596      2.707  2.591
Theta2 for idx -4.243 0.1483     -4.554   -4.235     -3.973 -4.204

Expected number of effective parameters(std dev): 404.96(18.67)
Number of equivalent replicates : 14.20 

Marginal log-Likelihood:  -19395.22 
# Fit model to point site with holes.


# Fit model to quadrat-sampled site.

References

Baddeley, Adrian, and Rolf Turner. 2005. “Spatstat: An R Package for Analyzing Spatial Point Patterns.” Journal of Statistical Software 12 (6): 1–42.

Blangiardo, Marta, and Michela Cameletti. 2015. Spatial and Spatio-Temporal Bayesian Models with R-INLA. Wiley.

Illian, Janine B, Sigrunn H Sørbye, and Håvard Rue. 2012. “A Toolbox for Fitting Complex Spatial Point Process Models Using Integrated Nested Laplace Approximation (Inla).” The Annals of Applied Statistics, 1499–1530.

Lindgren, Finn, Håvard Rue, and Johan Lindström. 2011. “An Explicit Link Between Gaussian Fields and Gaussian Markov Random Fields: The Stochastic Partial Differential Equation Approach.” Journal of the Royal Statistical Society: Series B (Statistical Methodology) 73 (4): 423–98.

Møller, J, and RP Waagepetersen. 2007. “Modern Spatial Point Process Modelling and Inference.” Scandinavian Journal of Statistics 34: 643–711.

Simpson, Daniel, Janine B Illian, Finn Lindgren, Sigrunn H Sørbye, and Havard Rue. 2016. “Going Off Grid: Computationally Efficient Inference for Log-Gaussian Cox Processes.” Biometrika 103 (1): 49–70.

LS0tCnRpdGxlOiAiU3BhdGlhbCBQcmVkaWN0aW9uIHdpdGggSU5MQSIKYXV0aG9yOiAiS2VubmV0aCBBLiBGbGFnZyIKYmlibGlvZ3JhcGh5OiAiLi4vcmVmZXJlbmNlcy5iaWIiCm91dHB1dDoKICBodG1sX25vdGVib29rOgogICAgZmlnX2hlaWdodDogNgogICAgZmlnX3dpZHRoOiAxMAogICAgZmlnX2Nyb3A6IEZBTFNFCiAgICBoZWlnaHQ6ICI5NjBweCIKICAgIHdpZHRoOiAiNzIwcHgiCiAgICBzZWxmX2NvbnRhaW5lZDogVFJVRQotLS0KCgpgYGB7ciBzZXR1cCwgY2FjaGUgPSBGQUxTRSwgZWNobyA9IEZBTFNFLCBtZXNzYWdlID0gRkFMU0UsIHdhcm5pbmcgPSBGQUxTRX0Ka25pdHI6Om9wdHNfY2h1bmskc2V0KGNhY2hlID0gRkFMU0UsIGVjaG8gPSBUUlVFLCB3YXJuaW5nID0gRkFMU0UsCiAgbWVzc2FnZSA9IEZBTFNFLCBkcGkgPSAxNTAsIGZpZy5hbGlnbiA9ICdjZW50ZXInKQpgYGAKCmBgYHtyIHBhY2thZ2VzLCBjYWNoZSA9IEZBTFNFLCBlY2hvID0gRkFMU0UsIG1lc3NhZ2UgPSBGQUxTRSwgd2FybmluZyA9IEZBTFNFfQpsaWJyYXJ5KHNwYXRzdGF0KQpsaWJyYXJ5KElOTEEpCmxpYnJhcnkoaW5sYWJydSkKbGlicmFyeShtYXB0b29scykKYGBgCgoKIyBJbnRyb2R1Y3Rpb24KClRoaXMgdmlnbmV0dGUgaWxsdXN0cmF0ZXMgdGhlIHVzZSBvZiBJTkxBIGZvciBzcGF0aWFsIHByZWRpY3Rpb24gdXNpbmcgZXhhbXBsZXMKZnJvbSBAcmlubGEgYW5kIEBpbGxpYW5ldGFsLiBGb3IgcHJlZGljdGlvbiBvZiBjb250aW51b3VzIHNwYXRpYWwgcHJvY2Vzc2VzLAp0aGUgc3RvY2hhc3RpYyBwYXJ0aWFsIGRpZmZlcmVudGlhbCBlcXVhdGlvbnMgKFNQREUpIGFwcHJvYWNoIGlzIHVzZWQgdG8KYXBwcm94aW1hdGUgdGhlIHByb2Nlc3MgdGhyb3VnaCBhbiBhcmVhbCBHYXVzc2lhbiBNYXJrb3YgcmFuZG9tIGZpZWxkIChHTVJGKQpyZXByZXNlbnRhdGlvbi4KCgojIEdNUkYgQmFja2dyb3VuZAoKQHJpbmxhIHNlY3Rpb24gNi4xLgoKLSBPYnNlcnZhdGlvbnMgYWdncmVnYXRlZCB0byBkaXNqb2ludCBhcmVhbCByZWdpb25zIGluZGV4ZWQgYnkgJGkkLgotIEVhY2ggcmVnaW9uIGhhcyB1bmlxdWUgcGFyYW1ldGVyICRcdGhldGFfe2l9JC4KLSAkXG1hdGhjYWx7Tn0oaSkkIGlzIHRoZSBzZXQgb2YgaW5kaWNlcyBvZiBuZWlnaGJvcnMgb2YgcmVnaW9uICRpJCBhbmQKICAkXG1hdGhjYWx7Tn1fe2l9ID0gfFxtYXRoY2Fse059KGkpfCQgaXMgdGhlIG51bWJlciBvZiBuZWlnaGJvciBvZiByZWdpb24gJGkkLgotIExvY2FsIE1hcmtvdiBwcm9wZXJ0eTogZ2l2ZW4gJFxib2xkc3ltYm9se1x0aGV0YX1fe1xtYXRoY2Fse059KGkpfSQsCiAgJFx0aGV0YV97aX0kIGlzIGluZGVwZW5kZW50IG9mIGFsbCBvdGhlciAkXHRoZXRhX3tqfSQuCi0gVGhlbiB0aGUgcHJlY2lzaW9uIG1hdHJpeCAkXG1hdGhiZntRfSQgb2YgJFxib2xkc3ltYm9se1x0aGV0YX0kIGlzIHNwYXJzZQogIGJlY2F1c2Ugb25seSBuZWlnaGJvcnMgaGF2ZSBub256ZXJvIGNvcHJlY2lzaW9ucy4KCi0gQmVzYWctWW9yay1Nb2xsaSYjeDAwZTg7IG1vZGVsOgogICAgLSBFeGNoYW5nZWFibGUgcmFuZG9tIGVmZmVjdHMgJHVfe2l9JCB3aXRoIGludHJpbnNpYyBjb25kaXRpb25hbAogICAgICBhdXRvcmVncmVzc2l2ZSAoaUNBUikgc3RydWN0dXJlLgogICAgLSAkdV97aX18XG1hdGhiZnt1fV97LWl9IFxzaW0gXG1hdGhybXtOfVxsZWZ0KFxtdV97aX0gKyBcc3VtX3tqfSBhX3tpan0gKHVfe2p9IC0gXG11X3tqfSkgLyBcbWF0aGNhbHtOfV97aX0sIFxzaWdtYV97dX1eezJ9IC8gXG1hdGhjYWx7Tn1fe2l9XHJpZ2h0KSQKICAgIC0gKFdoYXQgYXJlIHRoZSAkYV97aWp9PyQpLgogICAgLSBpQ0FSIGlzIGFuIGltcHJvcGVyIHByaW9yIGJlY2F1c2UgY292YXJpYW5jZSBtYXRyaXggbm90IHBvc2l0aXZlIGRlZmluaXRlCiAgICAgIGJ1dCB0aGlzIGlzIG9rIGZvciByYW5kb20gZWZmZWN0cy4KCgojIFNQREUgQmFja2dyb3VuZAoKKkZpbmQgTGluZGdyZW4gZXQuIGFsLiAoMjAxMSkgYW5kIGZpbGwgaW4gbW90aXZhdGlvbioKCi0gU3BhdGlhbCBwcm9jZXNzICRceGkoXG1hdGhiZntzfSkkLgoKLSBTb2x2ZSAkKFxrYXBwYV57Mn0gLSBcRGVsdGEpXntcYWxwaGEgLyAyfShcdGF1IFx4aShcbWF0aGJme3N9KSkgPSBcbWF0aGNhbHtXfShcbWF0aGJme3N9KSQuCiAgICAtICRca2FwcGEkIGlzIGEgcmFuZ2UgcGFyYW1ldGVyLgogICAgLSAkXERlbHRhJCBpcyB0aGUgTGFwbGFjaWFuLgogICAgLSAkXGFscGhhJCBpcyBhIHNtb290aG5lc3MgcGFyYW1ldGVyLgogICAgLSAkXHRhdSQgYSBwcmVjaXNpb24gcGFyYW1ldGVyLgogICAgLSBFeGFjdCBhbmQgc2F0aW9uYXJ5IHNvbHV0aW9uOiAkXHhpKFxtYXRoYmZ7c30pJCBpcyBhIEdhdXNzaWFuIGZpZWxkIHdpdGggTWF0JiN4MDBlODtybiBjb3ZhcmlhbmNlIGZ1bmN0aW9uLgoKLSBGaW5pdGUgZWxlbWVudCBhcHByb3hpbWF0aW9uICQkLgoKCiMgR2Vvc3RhdGlzdGljcyBFeGFtcGxlCgpUb3kgZGF0YXNldCBmcm9tIEByaW5sYS4KCmBgYHtyIHNwZGV0b3ksIGZpZy53aWR0aCA9IDYsIG91dC53aWR0aCA9ICc2MCUnfQojIFBsb3QgdGhlIGRhdGEuCnBsb3QoczIgfiBzMSwgY29sID0gcmdiKFNQREV0b3kkeSAvIG1heChTUERFdG95JHkpLCAwLCAwKSwgZGF0YSA9IFNQREV0b3ksIHBjaCA9IDE5LCBhc3AgPSAxLCBtYWluID0gJ1RveSBEYXRhJykKYGBgCgpgYGB7ciBzcGRlbWVzaCwgZmlnLndpZHRoID0gNiwgb3V0LndpZHRoID0gJzYwJSd9CiMgQ3JlYXRlIGEgbWVzaCBmb3IgdGhlIFNQREUgbWV0aG9kIGFuZCB0aGVuIHBsb3QgaXQuCnRveV9tZXNoIDwtIGlubGEubWVzaC4yZChhcy5tYXRyaXgoU1BERXRveVssYygnczEnLCAnczInKV0pLCBtYXguZWRnZSA9IGMoMC4xLCAwLjIpKQpwbG90KHRveV9tZXNoLCBhc3AgPSAxKQpwb2ludHMoU1BERXRveSRzMSwgU1BERXRveSRzMiwgY29sID0gcmdiKFNQREV0b3kkeSAvIG1heChTUERFdG95JHkpLCAwLCAwLCAwLjUpLCBwY2ggPSAyMCkKYGBgCgpgYGB7ciBzcGRlZml0fQojIFNQREUgcHJvamVjdG9yIG1hdHJpeCBmb3IgZXN0aW1hdGlvbi4KQV9lc3QgPC0gaW5sYS5zcGRlLm1ha2UuQSh0b3lfbWVzaCwgYXMubWF0cml4KFNQREV0b3lbLGMoJ3MxJywgJ3MyJyldKSkKCiMgSW5pdGlhbGl6ZSBleHBvbmVudGlhbCBjb3ZhcmlhbmNlIHN0cnVjdHVyZSBmb3IgU1BERS4Kc3BkZSA8LSBpbmxhLnNwZGUyLm1hdGVybihtZXNoID0gdG95X21lc2gsIGFscGhhID0gMikKCiMgU2V0IHVwIHN0YWNrIGZvciBlc3RpbWF0aW9uLgpzdGFja19pbmRleCA8LSBpbmxhLnNwZGUubWFrZS5pbmRleChuYW1lID0gJ3NwYXRpYWxfZmllbGQnLCBuLnNwZGUgPSBzcGRlJG4uc3BkZSkKc3RhY2tfZXN0IDwtIGlubGEuc3RhY2soZGF0YSA9IGxpc3QoeSA9IFNQREV0b3kkeSksIEEgPSBsaXN0KEFfZXN0KSwgZWZmZWN0cyA9IGxpc3QoYyhzdGFja19pbmRleCwgbGlzdChpbnRlcmNlcHQgPSAxKSkpLCB0YWcgPSAnZXN0JykKCiMgQ3JlYXRlIGEgZ3JpZCBmb3IgcHJlZGljdGlvbi4KdG95X254IDwtIDUwCnRveV9ueSA8LSA1MAp0b3lfZ3JpZCA8LSBleHBhbmQuZ3JpZCh4ID0gc2VxKDAsIDEsIGxlbmd0aC5vdXQgPSB0b3lfbngpLCB5ID0gc2VxKDAsIDEsIGxlbmd0aC5vdXQgPSB0b3lfbnkpKQoKIyBTUERFIHByb2plY3RvciBtYXRyaXggZm9yIHByZWRpY3Rpb24uCkFfcHJlZCA8LSBpbmxhLnNwZGUubWFrZS5BKG1lc2ggPSB0b3lfbWVzaCwgbG9jID0gYXMubWF0cml4KHRveV9ncmlkKSkKCiMgU2V0IHVwIHN0YWNrcyBmb3IgcHJlZGljdGlvbi4Kc3RhY2tfbGF0ZW50IDwtIGlubGEuc3RhY2soZGF0YSA9IGxpc3QoeGkgPSBOQSksIEEgPSBsaXN0KEFfcHJlZCksIGVmZmVjdHMgPSBsaXN0KHN0YWNrX2luZGV4KSwgdGFnID0gJ3ByZWRfbGF0ZW50JykKc3RhY2tfcmVzcG9uc2UgPC0gaW5sYS5zdGFjayhkYXRhID0gbGlzdCh5ID0gTkEpLCBBID0gbGlzdChBX3ByZWQpLCBlZmZlY3RzID0gbGlzdChjKHN0YWNrX2luZGV4LCBsaXN0KGludGVyY2VwdCA9IDEpKSksIHRhZyA9ICdwcmVkX3Jlc3BvbnNlJykKCiMgSm9pbiBhbGwgdGhyZWUgc3RhY2tzLgpzdGFja3MgPC0gaW5sYS5zdGFjayhzdGFja19lc3QsIHN0YWNrX2xhdGVudCwgc3RhY2tfcmVzcG9uc2UpCgojIEZpdCB0aGUgbW9kZWwgd2l0aCBJTkxBLgp0b3lfZml0IDwtIGlubGEoCiAgeSB+IC0xICsgaW50ZXJjZXB0ICsgZihzcGF0aWFsX2ZpZWxkLCBtb2RlbCA9IHNwZGUpLAogIGRhdGEgPSBpbmxhLnN0YWNrLmRhdGEoc3RhY2tzKSwKICBjb250cm9sLnByZWRpY3RvciA9IGxpc3QoQSA9IGlubGEuc3RhY2suQShzdGFja3MpLCBjb21wdXRlID0gVFJVRSkKKQoKIyBPdXRwdXQgcG9zdGVyaW9yIHN1bW1hcmllcy4KdG95X2ZpdCRzdW1tYXJ5LmZpeGVkCnRveV9maXQkc3VtbWFyeS5oeXBlcnBhcgoKIyBFeHRyYWN0IHBvc3RlcmlvciBtZWFuIG9mIGxhdGVudCBzcGF0aWFsIGZpZWxkLgppbmRleF9sYXRlbnQgPC0gaW5sYS5zdGFjay5pbmRleChzdGFja3MsIHRhZyA9ICdwcmVkX2xhdGVudCcpJGRhdGEKcG9zdF9tZWFuIDwtIHRveV9maXQkc3VtbWFyeS5saW5lYXIucHJlZGljdG9yW2luZGV4X2xhdGVudCwgJ21lYW4nXQpwb3N0X3NkIDwtIHRveV9maXQkc3VtbWFyeS5saW5lYXIucHJlZGljdG9yW2luZGV4X2xhdGVudCwgJ3NkJ10KCiMgUGxvdCB0aGUgcG9zdGVyaW9yIG1lYW4gYW5kIFNEIG9mIHRoZSBsYXRlbnQgc3BhdGlhbCBmaWVsZC4KcGxvdChpbShtYXRyaXgocG9zdF9tZWFuLCBucm93ID0gdG95X254LCBuY29sID0gdG95X255KSwgeHJhbmdlID0gcmFuZ2UodG95X2dyaWQkeCksIHlyYW5nZSA9IHJhbmdlKHRveV9ncmlkJHkpKSwgbWFpbiA9ICdQb3N0ZXJpb3IgTWVhbiBvZiBTcGF0aWFsIEZpZWxkJykKcG9pbnRzKFNQREV0b3kkczEsIFNQREV0b3kkczIsIGNvbCA9IHJnYihTUERFdG95JHkgLyBtYXgoU1BERXRveSR5KSwgMCwgMCwgMC41KSwgcGNoID0gMjApCnBsb3QoaW0obWF0cml4KHBvc3Rfc2QsIG5yb3cgPSB0b3lfbngsIG5jb2wgPSB0b3lfbnkpLCB4cmFuZ2UgPSByYW5nZSh0b3lfZ3JpZCR4KSwgeXJhbmdlID0gcmFuZ2UodG95X2dyaWQkeSkpLCBtYWluID0gJ1Bvc3RlcmlvciBTRCBvZiBTcGF0aWFsIEZpZWxkJykKcG9pbnRzKFNQREV0b3kkczEsIFNQREV0b3kkczIsIGNvbCA9IHJnYihTUERFdG95JHkgLyBtYXgoU1BERXRveSR5KSwgMCwgMCwgMC41KSwgcGNoID0gMjApCmBgYAoKCiMgQmVpIERhdGFzZXQgYW5kIGBpbmxhYnJ1YAoKRXhhbXBsZSBmcm9tIEBtb2VsbGVyd2FhZ2VwZXRlcnNlbiwgX0JlaWxzY2htaWVkaWEgcGVuZHVsYSBMYXVyYWNlYWVfIGxvY2F0aW9ucwppbiBhIHBsb3QgaW4gUGFuYW1hLiBgYmVpYCBkYXRhc2V0IGluIGBzcGF0c3RhdGAgW0BzcGF0c3RhdF0uCgpgYGB7ciBiZWlwdHN9CiMgUGxvdCB0aGUgZnVsbCBwb2ludCBwYXR0ZXJuLgpwbG90KGJlaSwgcGNoID0gJy4nLCBjb2xzID0gJ2JsYWNrJywgbWFpbiA9ICdSZWFsaXplZCBQb2ludCBQYXR0ZXJuJykKYGBgCgpgYGB7ciBiZWltZXNofQpiZWlfY29ybmVycyA8LSB2ZXJ0aWNlcy5vd2luKFdpbmRvdyhiZWkpKQpiZWlfZG9tYWluIDwtIGNiaW5kKGJlaV9jb3JuZXJzJHgsIGJlaV9jb3JuZXJzJHkpCmJlaV9mdWxsX21lc2ggPC0gaW5sYS5tZXNoLjJkKGNiaW5kKGJlaSR4LCBiZWkkeSksCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGN1dG9mZiA9IDUwLCBtYXguZWRnZSA9IGMoNTAsIDEwMCksCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGxvYy5kb21haW4gPSBiZWlfZG9tYWluKQpwbG90KGJlaV9mdWxsX21lc2gsIGFzcCA9IDEpCnBsb3QoV2luZG93KGJlaSksIGJvcmRlciA9ICdibHVlJywgYWRkID0gVFJVRSkKcG9pbnRzKGJlaSwgcGNoID0gJy4nLCBjb2wgPSAnYmx1ZScpCmBgYAoKYGBge3IgYmVpZnVsbGxnY3AsIGNhY2hlID0gVFJVRX0KYmVpX2Z1bGxfc3BkZiA8LSBhcy5TcGF0aWFsUG9pbnRzLnBwcChiZWkpCiMgQ0hFQ0sgUFJJT1JTIQptYXRlcm5fZnVsbCA8LSBpbmxhLnNwZGUyLnBjbWF0ZXJuKGJlaV9mdWxsX21lc2gsCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgcHJpb3Iuc2lnbWEgPSBjKDAuMSwgMC45OSksCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgcHJpb3IucmFuZ2UgPSBjKDUsIDAuMDEpKQpjbXBfZnVsbCA8LSBjb29yZGluYXRlcyB+IG15U21vb3RoKG1hcCA9IGNvb3JkaW5hdGVzLCBtb2RlbCA9IG1hdGVybl9mdWxsKSArIEludGVyY2VwdApiZWlfZnVsbF9sZ2NwIDwtIGxnY3AoY21wX2Z1bGwsIGJlaV9mdWxsX3NwZGYpCmxhbWJkYV9mdWxsIDwtIHByZWRpY3QoYmVpX2Z1bGxfbGdjcCwgcGl4ZWxzKGJlaV9mdWxsX21lc2gpLCB+IGV4cChteVNtb290aCArIEludGVyY2VwdCkpCgojIFBsb3QgcG9zdGVyaW9yIG1lYW5zIGFuZCBwb3N0ZXJpb3Igc2QuCnBsb3QobGFtYmRhX2Z1bGwpCnBsb3QoV2luZG93KGJlaSksIGJvcmRlciA9ICd3aGl0ZScsIGFkZCA9IFRSVUUpCnBvaW50cyhiZWksIHBjaCA9ICcuJywgY29sID0gJ3doaXRlJykKcGxvdChsYW1iZGFfZnVsbFsnc2QnXSkKcGxvdChXaW5kb3coYmVpKSwgYm9yZGVyID0gJ3doaXRlJywgYWRkID0gVFJVRSkKcG9pbnRzKGJlaSwgcGNoID0gJy4nLCBjb2wgPSAnd2hpdGUnKQpgYGAKCmBgYHtyIGJlaWhvbGV9CiMgVGFrZSBhIHNhbXBsZSBvZiBxdWFkcmF0cyBhbmQgcGxvdCB0aGUgb2JzZXJ2ZWQgcG9pbnQgcGF0dGVybi4Kc2V0LnNlZWQoODQzMjMpCm5fcXVhZHMgPC0gMTAKYm90bGVmdCA8LSBjYmluZChydW5pZihuX3F1YWRzLCAwLCA5NTApLCBydW5pZihuX3F1YWRzLCAwLCA0NTApKQpiZWlfaW50ZXJpb3IgPC0gbGFwcGx5KHNlcV9sZW4obnJvdyhib3RsZWZ0KSksIGZ1bmN0aW9uKHIpe3JldHVybigKICAgIGNiaW5kKAogICAgICBib3RsZWZ0W3IsIDFdICsgYygwLCAwLCA1MCwgNTApLAogICAgICBib3RsZWZ0W3IsIDJdICsgYygwLCA1MCwgNTAsIDApCiAgICApCiAgKX0pCmJlaV93aW4gPC0gZG8uY2FsbCgKICB1bmlvbi5vd2luLAogIGFwcGx5KGJvdGxlZnQsIDEsIGZ1bmN0aW9uKHgpe3JldHVybigKICAgIG93aW4oeFsxXSArIGMoMCwgNTApLCB4WzJdICsgYygwLCA1MCkpCiAgKX0pCikKYmVpX2hvbGUgPC0gYmVpW2NvbXBsZW1lbnQub3dpbihiZWlfd2luKV0KYmVpX3NhbXAgPC0gYmVpW2JlaV93aW5dCmJlaV93aW5kb3dfZnVsbCA8LSBXaW5kb3coYmVpKQoKcGxvdChiZWlfaG9sZSwgbWFpbiA9ICdPYnNlcnZlZCBTdWJyZWdpb24nLCBwY2ggPSAnLicsIGNvbHMgPSAnYmxhY2snKQpgYGAKCmBgYHtyIGJlaWhvbGVtZXNofQpiZWlfaG9sZV9tZXNoIDwtIGlubGEubWVzaC4yZChjYmluZChiZWlfaG9sZSR4LCBiZWlfaG9sZSR5KSwKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgY3V0b2ZmID0gNTAsIG1heC5lZGdlID0gYyg1MCwgMTAwKSwKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgbG9jLmRvbWFpbiA9IGJlaV9kb21haW4pCnBsb3QoYmVpX2hvbGVfbWVzaCwgYXNwID0gMSkKcGxvdChXaW5kb3coYmVpKSwgYm9yZGVyID0gJ2JsdWUnLCBhZGQgPSBUUlVFKQpwb2ludHMoYmVpX2hvbGUsIHBjaCA9ICcuJywgY29sID0gJ2JsdWUnKQpgYGAKCmBgYHtyIGJlaWhvbGVsZ2NwLCBjYWNoZSA9IFRSVUV9CmJlaV9ob2xlX3NwZGYgPC0gYXMuU3BhdGlhbFBvaW50cy5wcHAoYmVpX2hvbGUpCiMgQ0hFQ0sgUFJJT1JTIQptYXRlcm5faG9sZSA8LSBpbmxhLnNwZGUyLnBjbWF0ZXJuKGJlaV9ob2xlX21lc2gsCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgcHJpb3Iuc2lnbWEgPSBjKDAuMSwgMC45OSksCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgcHJpb3IucmFuZ2UgPSBjKDUsIDAuMDEpKQpjbXBfaG9sZSA8LSBjb29yZGluYXRlcyB+IG15U21vb3RoKG1hcCA9IGNvb3JkaW5hdGVzLCBtb2RlbCA9IG1hdGVybl9ob2xlKSArIEludGVyY2VwdApiZWlfaG9sZV9sZ2NwIDwtIGxnY3AoY21wX2hvbGUsIGJlaV9ob2xlX3NwZGYpCmxhbWJkYV9ob2xlIDwtIHByZWRpY3QoYmVpX2hvbGVfbGdjcCwgcGl4ZWxzKGJlaV9ob2xlX21lc2gpLCB+IGV4cChteVNtb290aCArIEludGVyY2VwdCkpCgojIFBsb3QgcG9zdGVyaW9yIG1lYW5zIGFuZCBwb3N0ZXJpb3Igc2QuCnBsb3QobGFtYmRhX2hvbGUpCnBsb3QoV2luZG93KGJlaV9ob2xlKSwgYm9yZGVyID0gJ3doaXRlJywgYWRkID0gVFJVRSkKcG9pbnRzKGJlaV9ob2xlLCBwY2ggPSAnLicsIGNvbCA9ICd3aGl0ZScpCnBsb3QobGFtYmRhX2hvbGVbJ3NkJ10pCnBsb3QoV2luZG93KGJlaV9ob2xlKSwgYm9yZGVyID0gJ3doaXRlJywgYWRkID0gVFJVRSkKcG9pbnRzKGJlaV9ob2xlLCBwY2ggPSAnLicsIGNvbCA9ICd3aGl0ZScpCmBgYAoKYGBge3IgYmVpc2FtcH0KcGxvdChiZWlfd2luZG93X2Z1bGwsIG1haW4gPSAnT2JzZXJ2ZWQgU2FtcGxlJykKcGxvdChiZWlfd2luLCBhZGQgPSBUUlVFKQpwbG90KGJlaV9zYW1wLCBwY2ggPSAnLicsIGNvbHMgPSAnYmxhY2snLCBhZGQgPSBUUlVFKQpgYGAKCmBgYHtyIGJlaXNhbXBtZXNofQpiZWlfc2FtcF9tZXNoIDwtIGlubGEubWVzaC4yZChjYmluZChiZWlfc2FtcCR4LCBiZWlfc2FtcCR5KSwKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgY3V0b2ZmID0gNTAsIG1heC5lZGdlID0gYyg1MCwgMTAwKSwKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgbG9jLmRvbWFpbiA9IGJlaV9kb21haW4pCnBsb3QoYmVpX3NhbXBfbWVzaCwgYXNwID0gMSkKcGxvdChXaW5kb3coYmVpKSwgYm9yZGVyID0gJ2JsdWUnLCBhZGQgPSBUUlVFKQpwbG90KFdpbmRvdyhiZWlfc2FtcCksIGJvcmRlciA9ICdibHVlJywgYWRkID0gVFJVRSkKcG9pbnRzKGJlaV9zYW1wLCBwY2ggPSAnLicsIGNvbCA9ICdibHVlJykKYGBgCgpgYGB7ciBiZWlzYW1wbGdjcCwgY2FjaGUgPSBUUlVFfQpiZWlfc2FtcF9zcGRmIDwtIGFzLlNwYXRpYWxQb2ludHMucHBwKGJlaV9zYW1wKQojIENIRUNLIFBSSU9SUyEKbWF0ZXJuX3NhbXAgPC0gaW5sYS5zcGRlMi5wY21hdGVybihiZWlfc2FtcF9tZXNoLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIHByaW9yLnNpZ21hID0gYygwLjEsIDAuOTkpLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIHByaW9yLnJhbmdlID0gYyg1LCAwLjAxKSkKY21wX3NhbXAgPC0gY29vcmRpbmF0ZXMgfiBteVNtb290aChtYXAgPSBjb29yZGluYXRlcywgbW9kZWwgPSBtYXRlcm5fc2FtcCkgKyBJbnRlcmNlcHQKYmVpX3NhbXBfbGdjcCA8LSBsZ2NwKGNtcF9zYW1wLCBiZWlfc2FtcF9zcGRmKQpsYW1iZGFfc2FtcCA8LSBwcmVkaWN0KGJlaV9zYW1wX2xnY3AsIHBpeGVscyhiZWlfc2FtcF9tZXNoKSwgfiBleHAobXlTbW9vdGggKyBJbnRlcmNlcHQpKQoKIyBQbG90IHBvc3RlcmlvciBtZWFucyBhbmQgcG9zdGVyaW9yIHNkLgpwbG90KGxhbWJkYV9zYW1wKQpwbG90KFdpbmRvdyhiZWkpLCBib3JkZXIgPSAnd2hpdGUnLCBhZGQgPSBUUlVFKQpwbG90KFdpbmRvdyhiZWlfc2FtcCksIGJvcmRlciA9ICd3aGl0ZScsIGFkZCA9IFRSVUUpCnBvaW50cyhiZWlfc2FtcCwgcGNoID0gJy4nLCBjb2wgPSAnd2hpdGUnKQpwbG90KGxhbWJkYV9zYW1wWydzZCddKQpwbG90KFdpbmRvdyhiZWkpLCBib3JkZXIgPSAnd2hpdGUnLCBhZGQgPSBUUlVFKQpwbG90KFdpbmRvdyhiZWlfc2FtcCksIGJvcmRlciA9ICd3aGl0ZScsIGFkZCA9IFRSVUUpCnBvaW50cyhiZWlfc2FtcCwgcGNoID0gJy4nLCBjb2wgPSAnd2hpdGUnKQpgYGAKCiMgQmVpIERhdGFzZXQgd2l0aCBncmlkZGluZwoKYGBge3IgYmVpaW5sYSwgY2FjaGUgPSBUUlVFfQpjZW50ZXJzIDwtIGdyaWRjZW50ZXJzKGRpbGF0aW9uKGJlaV93aW5kb3dfZnVsbCwgNDApLCA0MCwgMjApCmR4IDwtIHN1bSh1bmlxdWUoY2VudGVycyR4KVsxOjJdICogYygtMSwgMSkpIC8gMgpkeSA8LSBzdW0odW5pcXVlKGNlbnRlcnMkeSlbMToyXSAqIGMoLTEsIDEpKSAvIDIKYmVpX2RmIDwtIGRhdGEuZnJhbWUoeCA9IGNlbnRlcnMkeCwgeSA9IGNlbnRlcnMkeSwKICAgICAgICAgICAgICAgICAgICAgY291bnQgPSBOQV9pbnRlZ2VyXywgYXJlYSA9IE5BX3JlYWxfKQoKZm9yKHIgaW4gc2VxX2xlbihucm93KGJlaV9kZikpKXsKICBiZWlfZGYkY291bnRbcl0gPC0gc3VtKGJlaSR4ID49IGJlaV9kZiR4W3JdIC0gZHggJgogICAgICAgICAgICAgICAgICAgICAgICAgYmVpJHggPCBiZWlfZGYkeFtyXSArIGR4ICYKICAgICAgICAgICAgICAgICAgICAgICAgIGJlaSR5ID49IGJlaV9kZiR5W3JdIC0gZHkgJgogICAgICAgICAgICAgICAgICAgICAgICAgYmVpJHkgPCBiZWlfZGYkeVtyXSArIGR5KQogIGJlaV9kZiRhcmVhW3JdIDwtIGFyZWEoV2luZG93KGJlaSlbb3dpbihjKGJlaV9kZiR4W3JdIC0gZHgsIGJlaV9kZiR4W3JdICsgZHgpLCBjKGJlaV9kZiR5W3JdIC0gZHksIGJlaV9kZiR5W3JdICsgZHkpKV0pCn0KCnBhcihtYXIgPSBjKDAuNSwgMCwgMiwgMikpCnBsb3QoaW0odChtYXRyaXgoYmVpX2RmJGNvdW50LCBucm93ID0gbGVuZ3RoKHVuaXF1ZShiZWlfZGYkeCkpKSksIHVuaXF1ZShiZWlfZGYkeCksIHVuaXF1ZShiZWlfZGYkeSksIHVuaXRuYW1lID0gJ21ldGVycycpLCBuY29sY291cnMgPSByYW5nZShiZWlfZGYkY291bnQpICUqJSBjKC0xLCAxKSArIDEsIG1haW4gPSAnQmlubmVkIFRyZWUgQ291bnRzJykKcGxvdChiZWlfd2luZG93X2Z1bGwsIGJvcmRlciA9ICd3aGl0ZScsIGFkZCA9IFRSVUUpCnBvaW50cyhiZWksIHBjaCA9ICcuJywgY29sID0gJ2JsYWNrJykKCiMgU1BERSBwcm9qZWN0b3IgbWF0cml4IGZvciBlc3RpbWF0aW9uLgpmdWxsX0FfZXN0IDwtIGlubGEuc3BkZS5tYWtlLkEoYmVpX2Z1bGxfbWVzaCwgYXMubWF0cml4KGJlaV9kZltiZWlfZGYkYXJlYSA+IDAsIGMoJ3gnLCAneScpXSkpCgojIEluaXRpYWxpemUgZXhwb25lbnRpYWwgY292YXJpYW5jZSBzdHJ1Y3R1cmUgZm9yIFNQREUuCmZ1bGxfc3BkZSA8LSBpbmxhLnNwZGUyLm1hdGVybihtZXNoID0gYmVpX2Z1bGxfbWVzaCwgYWxwaGEgPSAyKQoKIyBTZXQgdXAgc3RhY2sgZm9yIGVzdGltYXRpb24uCnN0YWNrX2luZGV4IDwtIGlubGEuc3BkZS5tYWtlLmluZGV4KG5hbWUgPSAnc3BhdGlhbF9maWVsZCcsIG4uc3BkZSA9IGZ1bGxfc3BkZSRuLnNwZGUpCnN0YWNrX2VzdCA8LSBpbmxhLnN0YWNrKGRhdGEgPSBsaXN0KGNvdW50ID0gYmVpX2RmJGNvdW50W2JlaV9kZiRhcmVhID4gMF0sIGxhcmVhID0gbG9nKGJlaV9kZiRhcmVhW2JlaV9kZiRhcmVhID4gMF0pKSwgQSA9IGxpc3QoZnVsbF9BX2VzdCksIGVmZmVjdHMgPSBsaXN0KGMoc3RhY2tfaW5kZXgsIGxpc3QoaW50ZXJjZXB0ID0gMSkpKSwgdGFnID0gJ2VzdCcpCgojIFNQREUgcHJvamVjdG9yIG1hdHJpeCBmb3IgcHJlZGljdGlvbi4KZnVsbF9BX3ByZWQgPC0gaW5sYS5zcGRlLm1ha2UuQShtZXNoID0gYmVpX2Z1bGxfbWVzaCwgbG9jID0gYXMubWF0cml4KGJlaV9kZlssYygneCcsICd5JyldKSkKCiMgU2V0IHVwIHN0YWNrcyBmb3IgcHJlZGljdGlvbi4Kc3RhY2tfbGF0ZW50IDwtIGlubGEuc3RhY2soZGF0YSA9IGxpc3QoeGkgPSBOQSksIEEgPSBsaXN0KGZ1bGxfQV9wcmVkKSwgZWZmZWN0cyA9IGxpc3Qoc3RhY2tfaW5kZXgpLCB0YWcgPSAncHJlZF9sYXRlbnQnKQpzdGFja19yZXNwb25zZSA8LSBpbmxhLnN0YWNrKGRhdGEgPSBsaXN0KGNvdW50ID0gTkEpLCBBID0gbGlzdChmdWxsX0FfcHJlZCksIGVmZmVjdHMgPSBsaXN0KGMoc3RhY2tfaW5kZXgsIGxpc3QoaW50ZXJjZXB0ID0gMSkpKSwgdGFnID0gJ3ByZWRfcmVzcG9uc2UnKQoKIyBKb2luIGFsbCB0aHJlZSBzdGFja3MuCnN0YWNrcyA8LSBpbmxhLnN0YWNrKHN0YWNrX2VzdCwgc3RhY2tfbGF0ZW50LCBzdGFja19yZXNwb25zZSkKCiMgRml0IHRoZSBtb2RlbCB3aXRoIElOTEEuCmJlaV9mdWxsX2ZpdCA8LSBpbmxhKAogIGNvdW50IH4gLTEgKyBpbnRlcmNlcHQgKyBmKHNwYXRpYWxfZmllbGQsIG1vZGVsID0gZnVsbF9zcGRlKSwKICBvZmZzZXQgPSBsYXJlYSwgZmFtaWx5ID0gJ3BvaXNzb24nLAogIGRhdGEgPSBpbmxhLnN0YWNrLmRhdGEoc3RhY2tzKSwKICBjb250cm9sLnByZWRpY3RvciA9IGxpc3QoQSA9IGlubGEuc3RhY2suQShzdGFja3MpLCBjb21wdXRlID0gVFJVRSkKKQoKIyBPdXRwdXQgcG9zdGVyaW9yIHN1bW1hcmllcy4KYmVpX2Z1bGxfZml0JHN1bW1hcnkuZml4ZWQKYmVpX2Z1bGxfZml0JHN1bW1hcnkuaHlwZXJwYXIKCiMgRXh0cmFjdCBwb3N0ZXJpb3IgbWVhbiBvZiBsYXRlbnQgc3BhdGlhbCBmaWVsZC4KaW5kZXhfcHJlZCA8LSBpbmxhLnN0YWNrLmluZGV4KHN0YWNrcywgdGFnID0gJ3ByZWRfbGF0ZW50JykkZGF0YQpwb3N0X21lYW4gPC0gYmVpX2Z1bGxfZml0JHN1bW1hcnkubGluZWFyLnByZWRpY3RvcltpbmRleF9wcmVkLCAnbWVhbiddCnBvc3Rfc2QgPC0gYmVpX2Z1bGxfZml0JHN1bW1hcnkubGluZWFyLnByZWRpY3RvcltpbmRleF9wcmVkLCAnc2QnXQoKIyBQbG90IHRoZSBwb3N0ZXJpb3IgbWVhbiBhbmQgU0Qgb2YgdGhlIGxhdGVudCBzcGF0aWFsIGZpZWxkLgpwbG90KGltKHQobWF0cml4KHBvc3RfbWVhbiwgbnJvdyA9IGxlbmd0aCh1bmlxdWUoY2VudGVycyR4KSksIG5jb2wgPSBsZW5ndGgodW5pcXVlKGNlbnRlcnMkeSkpKSksIHVuaXF1ZShjZW50ZXJzJHgpLCB1bmlxdWUoY2VudGVycyR5KSksIG1haW4gPSAnUG9zdGVyaW9yIE1lYW4gb2YgU3BhdGlhbCBGaWVsZCcpCnBsb3QoYmVpX3dpbmRvd19mdWxsLCBhZGQgPSBUUlVFKQpwb2ludHMoYmVpLCBwY2ggPSAnLicsIGNvbCA9ICdibGFjaycpCnBsb3QoaW0odChtYXRyaXgocG9zdF9zZCwgbnJvdyA9IGxlbmd0aCh1bmlxdWUoY2VudGVycyR4KSksIG5jb2wgPSBsZW5ndGgodW5pcXVlKGNlbnRlcnMkeSkpKSksIHVuaXF1ZShjZW50ZXJzJHgpLCB1bmlxdWUoY2VudGVycyR5KSksIG1haW4gPSAnUG9zdGVyaW9yIFNEIG9mIFNwYXRpYWwgRmllbGQnKQpwbG90KGJlaV93aW5kb3dfZnVsbCwgYWRkID0gVFJVRSkKcG9pbnRzKGJlaSwgcGNoID0gJy4nLCBjb2wgPSAnYmxhY2snKQpgYGAKCmBgYHtyIGJlaWhvbGVpbmxhfQpiZWlob2xlX2RmIDwtIGRhdGEuZnJhbWUoeCA9IGNlbnRlcnMkeCwgeSA9IGNlbnRlcnMkeSwKICAgICAgICAgICAgICAgICAgICAgICAgIGNvdW50ID0gTkFfaW50ZWdlcl8sIGFyZWEgPSBOQV9yZWFsXykKCmZvcihyIGluIHNlcV9sZW4obnJvdyhiZWlob2xlX2RmKSkpewogIGJlaWhvbGVfZGYkY291bnRbcl0gPC0gc3VtKGJlaV9ob2xlJHggPj0gYmVpaG9sZV9kZiR4W3JdIC0gZHggJgogICAgICAgICAgICAgICAgICAgICAgICAgICAgIGJlaV9ob2xlJHggPCBiZWlob2xlX2RmJHhbcl0gKyBkeCAmCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgYmVpX2hvbGUkeSA+PSBiZWlob2xlX2RmJHlbcl0gLSBkeSAmCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgYmVpX2hvbGUkeSA8IGJlaWhvbGVfZGYkeVtyXSArIGR5KQogIGJlaWhvbGVfZGYkYXJlYVtyXSA8LSBhcmVhKFdpbmRvdyhiZWlfaG9sZSlbb3dpbihjKGJlaWhvbGVfZGYkeFtyXSAtIGR4LCBiZWlob2xlX2RmJHhbcl0gKyBkeCksIGMoYmVpaG9sZV9kZiR5W3JdIC0gZHksIGJlaWhvbGVfZGYkeVtyXSArIGR5KSldKQp9CgpwYXIobWFyID0gYygwLjUsIDAsIDIsIDIpKQpwbG90KGltKHQobWF0cml4KGJlaWhvbGVfZGYkY291bnQsIG5yb3cgPSBsZW5ndGgodW5pcXVlKGJlaWhvbGVfZGYkeCkpKSksIHVuaXF1ZShiZWlob2xlX2RmJHgpLCB1bmlxdWUoYmVpaG9sZV9kZiR5KSwgdW5pdG5hbWUgPSAnbWV0ZXJzJyksIG5jb2xjb3VycyA9IHJhbmdlKGJlaWhvbGVfZGYkY291bnQpICUqJSBjKC0xLCAxKSArIDEsIG1haW4gPSAnQmlubmVkIFRyZWUgQ291bnRzJykKcGxvdChXaW5kb3coYmVpX2hvbGUpLCBib3JkZXIgPSAnd2hpdGUnLCBhZGQgPSBUUlVFKQpwb2ludHMoYmVpLCBwY2ggPSAnLicsIGNvbCA9ICcjMDAwMDAwNDAnKQpgYGAKCgojIEJlaSBEYXRhc2V0IHdpdGggQHNpbXBzb25ldGFsIG1ldGhvZAoKVGhpcyBtZXRob2QgcmVsaWVzIHVwb24gdGhlIEBsaW5kZ3JlbmV0YWwgYXBwcm94aW1hdGlvbiBvZiB0aGUgbGF0ZW50IEdhdXNzaWFuCmZpZWxkIGFzIGEgbGluZWFyIGNvbWJpbmF0aW9uIG9mIGEgZmluaXRlIG51bWJlciBvZiBiYXNpcyBmdW5jdGlvbnMgcmVwcmVzZW50ZWQKYXMgYSBHTVJGIG9uIHRoZSBub2RlcyBvZiBhIHRyaWFuZ3VsYXRpb24gb2YgdGhlIHNwYWNlLiBAc2ltcHNvbmV0YWwgdXNlIHRoZQp0cmlhbmd1bGF0aW9uIGZvciBudW1lcmljYWwgaW50ZWdyYXRpb24gb2YgdGhlIGludGVuc2l0eSBmdW5jdGlvbiBhbmQgc2hvdyB0aGF0CnRoZSBMR0NQIGxpa2VsaWhvb2QgZmFjdG9ycyBpbnRvIHRoZSBqb2ludCBkaXN0cmlidXRpb24gb2YgaW5kZXBlbmRlbnQgUG9pc3NvbgpyYW5kb20gdmFyaWFibGVzIGNvcnJlc3BvbmRpbmcgdG8gdGhlIHBvaW50cyBvZiB0aGUgcG9pbnQgcGF0dGVybiBhbmQgdGhlIG5vZGVzCm9mIHRoZSB0cmlhbmd1bGF0aW9uLiBUaGUgbW9kZWwgZml0dGluZyBwcm9jZWVkcyB1c2luZyBJTkxBIHRvIGZpdCBhIFBvaXNzb24KbW9kZWwgdG8gcHNldWRvZGF0YS4KClRoZSBwc2V1ZG9kYXRhIGFyZSBjb25zdHJ1Y3RlZCBhcyBmb2xsb3dzLgoKLSBMZXQgJG4kIGJlIHRoZSBzaXplIG9mIHRoZSBwb2ludCBwYXR0ZXJuLgotIExldCAkcCQgYmUgdGhlIG51bWJlciBvZiBub2RlcyBvZiB0cmlhbmd1bGF0aW9uLgotIERlZmluZSB0aGUgcHNldWRvZGF0YSBhcwogICRcbWF0aGJme3l9ID0gKHlfezF9LCBcZG90cywgeV97cH0sIHlfe3ArMX0sIFxkb3RzLCB5X3twK259KSckIHdoZXJlCiAgJHlfe2l9ID0gMCQgZm9yICRpID0gMSwgXGRvdHMsIHAkICh0aGUgdHJhaW5ndWxhdGlvbiBub2RlcykgYW5kICR5X3tpfSA9IDEkCiAgZm9yICRpID0gcCsxLCBcZG90cywgcCtuJCAodGhlIG9ic2VydmVkIHBvaW50cykuCi0gRGVmaW5lICRcYm9sZHN5bWJvbHtcYWxwaGF9ID0gKFxhbHBoYV97aX0sIFxkb3RzLCBcYWxwaGFfe3B9LAogIFxhbHBoYV97cCsxfSwgXGRvdHMsIFxhbHBoYV97cCtufSknJCB0byBlbmNvZGUgdGhlIG51bWVyaWNhbCBpbnRlZ3JhdGlvbgogIHNjaGVtZSB3aGVyZSAkXGFscGhhX3tpfSQgaXMgdGhlIG51bWVyaWNhbCBpbnRlZ3JhdGlvbiB3ZWlnaHQgZm9yCiAgJGkgPSAxLCBcZG90cywgcCQgKHRoZSB0cmFpbmd1bGF0aW9uIG5vZGVzKSBhbmQgJFxhbHBoYV97aX0gPSAwJCAgIGZvcgogICRpID0gcCsxLCBcZG90cywgcCtuJCAodGhlIG9ic2VydmVkIHBvaW50cykuCgpUaGVuICR5X3tpfSBcc2ltIFBvaXNzb24oXGFscGhhX3tpfVxldGFfe2l9KSQgd2hlcmUgJFxsb2coXGV0YV97aX0pJCBpcyB0aGUKU1BERSByZXByZXNlbnRhdGlvbiBvZiB0aGUgR0YgYXQgdGhlIGxvY2F0aW9uIG9mIHRoZSAkaSR0aCBwc2V1ZG9kYXR1bS4gU2VlCnRoZSBwYXBlciBmb3IgdGVkaW91cyBub3RhdGlvbiByZWdhcmRpbmcgdGhlIGRlZmluaXRpb24gb2YgJFxldGFfe2l9JC4KVWx0aW1hdGVseSwgdGhlIG5vZGVzIGJlY29tZSBQb2lzc29uIHJhbmRvbSB2YXJpYWJsZXMgd2l0aCBtZWFucyBlcXVhbCB0byB0aGUKaW50ZW5zaXR5IGF0IHRoYXQgdGhlaXIgcmVzcGVjdGl2ZSBsb2NhdGlvbnMsIG9ic2VydmVkIHBvaW50cyBiZWNvbWUgUG9pc3NvbgpyYW5kb20gdmFyaWFibGVzIHdpdGggbWVhbnMgb2YgMSwgYW5kIHRoZSBsaWtlbGlob29kIGlzIGFwcHJveGltYXRlbHkKcHJvcG9ydGlvbmFsIHRvCgokJApccHJvZF97aT0xfV57cCtufSBcZXRhX3tpfV57eV97aX19IFxleHAoLVxhbHBoYV97aX0gXGV0YV97aX0pLgokJCAKCl8oSXMgdGhlcmUgYSBtaXNzaW5nICRcYWxwaGFfe2l9JD8pXwoKCmBgYHtyIGJlaW5vZ3JpZCwgbWVzc2FnZSA9IEZBTFNFLCBjYWNoZSA9IFRSVUV9CiMgUGFyYW1ldGVycyB0byBleHBlcmltZW50IHdpdGguCk1BWF9FREdFX0xFTkdUSCA8LSAyNQoKYm91bmRhcnkgPC0gaW5sYS5tZXNoLnNlZ21lbnQobG9jID0gZG8uY2FsbChjYmluZCwgdmVydGljZXMub3dpbihXaW5kb3coYmVpKSkpKQptZXNoIDwtIGlubGEubWVzaC5jcmVhdGUoCiAgYm91bmRhcnkgPSBib3VuZGFyeSwKICByZWZpbmUgPSBsaXN0KG1heC5lZGdlID0gTUFYX0VER0VfTEVOR1RIKQopCgpwbG90KG1lc2gsIG1haW4gPSAnTWVzaCBmb3IgQmVpIFNpdGUnKQpwb2ludHMoYmVpLCBwY2ggPSAxOSwgY2V4ID0gMC4yNSwgY29sID0gJ3JlZCcpCgpwdHMgPC0gY2JpbmQoYmVpJHgsIGJlaSR5KQoKIyBDb250cnVjdCB0aGUgU1BERSBBIG1hdHJpeCBmb3Igbm9kZXMgYW5kIHBvaW50cy4KblYgPC1tZXNoJG4KbkRhdGEgPC0gZGltKHB0cylbMV0KTG9jYXRpb25NYXRyaXggPC0gaW5sYS5tZXNoLnByb2plY3QobWVzaCwgcHRzKSRBCkludGVncmF0aW9uTWF0cml4IDwtIHNwYXJzZU1hdHJpeChpID0gMTpuViwgaiA9IDE6blYsIHggPSByZXAoMSwgblYpKQpPYnNlcnZhdGlvbk1hdHJpeCA8LSByYmluZChJbnRlZ3JhdGlvbk1hdHJpeCwgTG9jYXRpb25NYXRyaXgpCgojIEdldCB0aGUgaW50ZWdyYXRpb24gd2VpZ2h0cy4KSW50ZWdyYXRpb25XZWlnaHRzIDwtIGRpYWcoaW5sYS5tZXNoLmZlbShtZXNoKSRjMCkKRV9wb2ludF9wcm9jZXNzIDwtIGMoSW50ZWdyYXRpb25XZWlnaHRzLCByZXAoMCwgbkRhdGEpKQoKIyBDcmVhdGUgdGhlIHBzdWVkb2RhdGEuCmZha2VfZGF0YSA8LSBjKHJlcCgwLCBuViksIHJlcCgxLCBuRGF0YSkpCgojIEZpdCBtb2RlbCB0byBmdWxsIHNpdGUuCnNwZGUgPC0gaW5sYS5zcGRlMi5tYXRlcm4obWVzaCkKZm9ybXVsYSA8LSB5IH4gLTEgKyBpbnRlcmNlcHQgKyBmKGlkeCwgbW9kZWwgPSBzcGRlKSAjIE5vIGNvdmFyaWF0ZXMuCmRhdGEgPC0gbGlzdCh5ID0gZmFrZV9kYXRhLCBpZHggPSAxOihuViksIGludGVyY2VwdCA9IHJlcCgxLCBuVikpCnJlc3VsdF9mdWxsIDwtIGlubGEoCiAgZm9ybXVsYSwKICBkYXRhID0gZGF0YSwKICBmYW1pbHkgPSAncG9pc3NvbicsCiAgY29udHJvbC5wcmVkaWN0b3IgPSBsaXN0KEEgPSBPYnNlcnZhdGlvbk1hdHJpeCksCiAgRSA9IEVfcG9pbnRfcHJvY2VzcywKICB2ZXJib3NlID0gVFJVRQopCnN1bW1hcnkocmVzdWx0X2Z1bGwpCgoKIyBGaXQgbW9kZWwgdG8gcG9pbnQgc2l0ZSB3aXRoIGhvbGVzLgoKCiMgRml0IG1vZGVsIHRvIHF1YWRyYXQtc2FtcGxlZCBzaXRlLgpgYGAKCgojIFJlZmVyZW5jZXMKCg==